Conventional computer systems often include on-chip or off-chip cache memories (or caches) that are used to speed up accesses to system memory (or main memory). In a shared memory multiprocessor system, a cache memory (or cache) may also be shared. Typically, such a cache is referred to as a level-two cache, where dedicated level-one cache memories may be assigned to individual processors. The level-two cache memory commonly sits between the level-one cache memories and main memory. A level-one cache memory provides relatively low capacity, but fast access to an associated dedicated processor. A level-two cache memory services level-one cache misses (i.e., a failed attempt to read or write a piece of data in the cache) with somewhat increased latency, but offers substantially more capacity. Main memory, on the other hand, provides mass storage at the expense of greatly extended latency.
When a level-one cache memory misses, the associated dedicated processor may stall. From a system-level perspective such a stall may be tolerable since not all processors are idle for the duration of an idle period. However, stalls in a level-two cache memory have a bigger impact on system-level performance because all processors may be affected. Therefore measures may be taken to avoid, or minimise, conditions leading to a level-two cache memory stall. For example, when a cache miss occurs, the level-two cache memory may be configured to access main memory to fill a cache line. If a subsequent cache hit occurs (i.e., a successful attempt to read or write a piece of data in the cache) to the same cache line, the cache memory has no way to process the hit until the cache line is filled. To avoid stalling, the cache memory may buffer the hit until such time as the cache line is filled thereby allowing subsequent accesses to be processed.
A cache memory is subdivided into sets of cache lines. When each set contains just one cache line, each main memory line may be stored in just one location within the cache memory. Such a cache memory is referred to as a direct mapped cache memory. More typically, each set contains a number of cache lines. Each main memory line maps to a set and may therefore be stored in any of the cache lines (or ways) within the set. The method used for deciding which line in the set is to be replaced after a cache miss is called a “replacement policy”. One known method is to identify a least-recently-used cache line as the replacement, or “victim”, cache line. However, because a cache memory may buffer transactions that cannot be processed immediately, simple replacement methods may be inadequate. Steps need to be taken to ensure that any outstanding accesses to victim cache lines are completed before the victim cache line is replaced.
Thus a need clearly exists for an improved method of replacing data stored within a cache line, which avoids stalling dedicated processors.